package medium.前缀和;

import java.util.Arrays;

/**
 * 1738. 找出第 K 大的异或坐标值
 * 创建时间： 2024-05-26 9:48
 * 地址：https://leetcode.cn/problems/find-kth-largest-xor-coordinate-value/description/?envType=daily-question&envId=2024-05-26
 **/
public class 找出第K大的异或坐标值_1738 {

}

/**
 * 题解（看得懂）：https://leetcode.cn/problems/find-kth-largest-xor-coordinate-value/solutions/784300/zhao-chu-di-k-da-de-yi-huo-zuo-biao-zhi-mgick/?envType=daily-question&envId=2024-05-26
 */
class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] ans = new int[m * n];
        int[][] pre = new int[m + 1][n + 1];
        int idx = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pre[i + 1][j + 1] = pre[i][j + 1] ^ pre[i + 1][j] ^ pre[i][j] ^ matrix[i][j];
                ans[idx++] = pre[i + 1][j + 1];
            }
        }
        Arrays.sort(ans);
        return ans[idx - k];
    }
}
